def max_square(board):
    m = len(board)
    n = len(board[0])
    dp = [[0] * n for i in range(m)]
    for i in range(m):
        for j in range(n):
            val = board[i][j]
            # current val is 0, then 0
            if val == 0:
                dp[i][j] = 0
                continue
            # check left/up/up_left
            left = 0 if i < 1 else dp[i - 1][j]
            up = 0 if j < 1 else dp[i][j - 1]
            up_left = 0 if i < 1 or j < 1 else dp[i - 1][j - 1]
            dp[i][j] = min(left, up, up_left) + 1
    return pow(max(max(i) for i in dp), 2)


board = [[1, 0, 1, 0, 0], [1, 0, 1, 1, 1], [1, 1, 1, 1, 1], [1, 0, 0, 1, 0]]

print(max_square(board))
